# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        def advance(head, leng):
            while leng>0:
                head = head.next
                leng-=1
            return head
        def length(head):
            leng = 0
            while head:
                head = head.next
                leng+=1
            return leng
        leng = length(head)
        newHead = ListNode(None) 
        head1 = newHead
        head1.next = head
        head = advance(head1, leng//2)
        tail1 = head
        head = head.next
        mid = None
        if leng%2==1:
            mid = head
            head = head.next
        last = None
        while head:
            next = head.next
            head.next = last
            last = head
            head = next
        head = head1
        head1 = head1.next
        head2 = last
        head.next = None
        while head1 and head2:
            head.next = head1
            head1 = head1.next
            head = head.next
            head.next = head2
            head2 = head2.next
            head = head.next
            head.next = None
        if mid:
            head.next = mid
            head = head.next
            head.next = None
        return newHead.next

head = ListNode(0)
head = Solution().reorderList(head)
        